{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "H6rVIpdcxrUk" }, "source": [ "$\\newcommand\\indi[1]{{\\mathbf 1}_{\\displaystyle #1}}$\n", "$\\newcommand\\inde[1]{{\\mathbf 1}_{\\displaystyle\\left\\{ #1 \\right\\}}}$\n", "$\\newcommand{\\ind}{\\inde}$\n", "$\\newcommand\\E{{\\mathbf E}}$\n", "$\\newcommand\\P{{\\mathbf P}}$\n", "$\\newcommand\\Cov{{\\mathbf Cov}}$\n", "$\\newcommand\\Var{{\\mathbf Var}}$" ] }, { "cell_type": "markdown", "metadata": { "id": "rzsspKn6HWxu" }, "source": [ "# **
Décision dans l'incertain:
**\n", "\n", "\n", "##
Un exemple simple de problème de décision
" ] }, { "cell_type": "markdown", "metadata": { "id": "6RjNy6_WACZH" }, "source": [ "\n", " \n", "\n", " \n", " \n", "
\n", " \n", " \n", " Page du cours\n", "\n", " \n", " \n", " Colab\n", " \n", " Télécharger le Jupyter\n", "
" ] }, { "cell_type": "markdown", "metadata": { "id": "WzCEFt4WxrUr" }, "source": [ "# 1. La question à résoudre" ] }, { "cell_type": "markdown", "metadata": { "id": "2P3YE_XcxrUr" }, "source": [ " On place deux oeufs \"au hasard\" dans une matrice $p\\times q$. On\n", " considère deux joueurs ($A$ et $B$). Le joueur $A$ parcours la\n", " matrice en colonne, le joueur $B$ en ligne. Le gagnant est celui qui\n", " atteint le premier l'un des deux oeufs. La question est de savoir si\n", " ce jeu est équitable (i.e. les deux joueurs ont ils la même\n", " probabilité de gagner ?) et de déterminer, si ce n'est pas le cas,\n", " lequel a un avantage.\n", "\n", "\n", "
\n", "\n", "On trouvera la réponse à cette question lorsque $p=3$ et $q=4$ sur le\n", "site de la NSA. Nous verrons que l'on peut répondre très simplement\n", "à ces questions à l'aide d'un programme de quelques lignes pour une valeur\n", "arbitraire de $p$ et $q$. \n", "\n", "\n", "Les réponses dépendent des\n", "valeurs de $p$ et $q$ de façon surprenante: elles sont différentes\n", "pour $(p=3,q=4)$, $(p=4,q=4)$ et $(p=4,q=5)$!\n", "\n", "---\n", "\n", "Remarque:\n", "
\n", "Lorsque vous aurez terminé la partie informatique, les parties en bleu pourront\n", "vous servir d'exercices (de révision du cours du premier semestre).\n", "\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "id": "UQnnlFQ6xrUs" }, "source": [ "# 2. Étude de la question posée par une méthode de Monte-Carlo" ] }, { "cell_type": "markdown", "metadata": { "id": "1vv0cMmIxrUs" }, "source": [ "On commence par traiter la question par simulation. On suppose (ce qui\n", "est implicite dans la formulation du problème) que les $2$ oeufs\n", "sont placés, indépendamment, uniformément sur les $p\\times q$ cases de\n", "la matrice. Il peut donc arriver que les $2$ oeufs soient au même\n", "endroit (à vrai dire le problème ne précise pas ce détail), mais on\n", "verra que cela n'a pas d'importance pour la réponse à la question posée." ] }, { "cell_type": "markdown", "metadata": { "id": "50mnYcLWxrUs" }, "source": [ "### Simulation d'une loi discrète" ] }, { "cell_type": "markdown", "metadata": { "id": "e5azPbMoXSI5" }, "source": [ "**Rappel:**\n", "\n", "Il est possible de simuler une variable aléatoire qui prend les valeurs $(x_i)_{i\\in \\mathbb{N}^*}$ avec probabilités respectives $(p_i)_{i \\in \\mathbb{N}^*}$ (avec les $p_i \\geq 0$ et $\\sum\\limits_{i \\in \\mathbb{N}^*} p_i = 1$) à l'aide d'une seule variable aléatoire $U \\sim \\mathcal{U}([0, 1])$ en posant:\n", "\n", "$$\n", "X = x_1 \\mathbb{1}_{ \\{U \\leq p_1 \\} } + x_2 \\mathbb{1}_{ \\{p_1 \\leq U \\leq p_1 + p_2 \\}} + \\dots + x_i \\mathbb{1}_{ \\{p_1 + \\dots + p_{i-1} \\leq U \\leq p_1 + \\dots + p_i \\}} + \\dots\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": { "id": "yQRy-2TZxrUs" }, "source": [ "On cherche à réaliser un tirage selon la loi d'une variable aléatoire $N$ qui prend ses valeurs \n", "dans $\\{1,\\ldots,n\\}$ dont la loi donnée par le vecteur $(P[k-1],1\\leq k \\leq n)$.\n", "\n", "---\n", "Exercice 1:\n", "
\n", "Lorsque la loi est uniforme sur $\\{1,\\ldots,n\\}$, on peut\n", "vérifier (exercice) que $\\E(N)=\\frac{n+1}{2}$ et $\\Var(N)=\\frac{(n+1)(n-1)}{12}$.\n", "\n", "\n", "---\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "0G3xCWCwxrUt" }, "outputs": [], "source": [ "import random\n", "import numpy as np\n", "import math\n", "\n", "def rand_disc(P):\n", "# P est une loi discrète qui charge les entiers 1,...,p\n", "# le vecteur P[i-1],pour i=1,...,p donne la probabilité d'obtenir i .\n", "# Il est décalé de 1 pour tenir compte de la convention \"Python\"\n", "# de vecteur qui débute en 0.\n", "\n", "# Version itérative.\n", " U=np.random.rand(1) # On tire selon une loi uniforme entre 0 et 1\n", " # \"On inverse la fonction de répartition\" : voir cours du premier semestre.\n", "\n", " ###### A vous de jouer .....\n", " " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "LCFPvgKglo02", "outputId": "50b69098-5f04-462d-df43-59a1c7092baf" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "moyenne empirique: 6.399 - moyenne attendue 6.5\n", "variance: 12.239799 - variance attendue 11.916666666666666\n" ] } ], "source": [ "n=12\n", "P=np.ones(n)/n\n", "X=np.zeros(1000,dtype=int) # dtype=int pour indiquer que le tableau est constitué d'entiers\n", "for i in range(1000):\n", " X[i]=rand_disc(P)\n", "print(\"moyenne empirique:\",np.mean(X),\" - moyenne attendue \",(n+1)/2) # np.mean calcule moyenne des tirages\n", "print(\"variance:\",np.var(X),\" - variance attendue \",(n+1)*(n-1)/12) # np.var la variance des tirages" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "qJqCddHZxrUu", "outputId": "919c16ca-2a6a-464a-9cf7-8574f0def2af" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3 1 3 1 2 3 3 1 3 2 " ] } ], "source": [ "def test_0():\n", "# Un exemple de tirages uniformes sur |$\\{1,2,3\\}$|\n", " p=3;\n", " P=np.ones(p)/p;# loi uniforme sur |$\\{1,2,3\\}$|\n", "\n", " N=10;\n", " X=np.zeros(N,dtype=int)\n", " for i in range(N): # N tirages uniformes sur |$\\{1,2,3\\}$|\n", " X[i] = rand_disc(P)\n", " print(X[i], end=' ')\n", " \n", "test_0()" ] }, { "cell_type": "markdown", "metadata": { "id": "hhNP_U55xrUu" }, "source": [ "### Simulation des temps d'atteinte" ] }, { "cell_type": "markdown", "metadata": { "id": "lWuzduO0xrUv" }, "source": [ "On tire le premier oeuf en $(U_1,V_1)$, $U_1$ (l'indice de ligne)\n", "et $V_1$ (l'indice de colonne) étant indépendantes, de loi uniforme\n", "respectivement sur $\\{1,\\ldots,p\\}$ et $\\{1,\\ldots,q\\}$. Si le premier\n", "oeuf se trouve en $(U_1,V_1)$, le temps d'atteinte de cet oeuf\n", "par $A$ (parcours en colonne) est donné par\n", "$$\n", " t_1^A=(V_1-1) p+U_1,\n", "$$\n", "\n", "
\n", "\n", "et, pour $B$ (parcours en ligne), par\n", "$$\n", "t_1^B=(U_1-1) q+V_1,\n", "$$\n", "
\n", "avec des formules identiques pour le deuxième oeuf:\n", "$$\n", "t_2^A=(V_2-1) p+U_2,\\quad t_2^B=(U_2-1) q+V_2,\n", "$$ \n", "$U_2$ et $V_2$ étant indépendantes, toujours de lois uniformes,\n", "indépendantes du couple $(U_1,V_1)$.\n", "\n", "---\n", "Exercice 2:\n", "
\n", " Noter que l'on peut calculer la loi (commune) de $t_1^A$, $t_1^B$,\n", "$t_2^A$, $t_2^B$ (loi uniforme sur $\\{1,\\ldots,p\\times q\\}$) et\n", "montrer que $t_1^A$ s'obtient comme une permutation déterministe $\\sigma$ de\n", "$t_1^B$.\n", "\n", "\n", "---\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "hotE62_COYIm" }, "source": [ "Avec ces éléments, il est facile d'écrire une fonction qui réalise le tirage\n", "des deux oeufs dans la matrice et d'en déduire les temps que mettent $A$\n", "et $B$ pour trouver le premier oeuf (au sens chronologique).\n", "\n", "En d'autres termes:\n", "\n", "$$\n", "T_A = \\min(t_1^A, t_2^A), \\quad T_B = \\min(t_1^B, t_2^B)\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "id": "PG7O10UcL-zv" }, "source": [ "\n", "---\n", "Exercice 3:\n", "
\n", "Montrer que $T_A$ et $T_B$ ont la même loi et que si $\\sigma^2 = id$ alors les couples $(T_A, T_B)$ et $(T_b, T_A)$ ont la même loi (c'est la cas lorsque $p=q$).\n", "\n", "\n", "---\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "id": "MdU7jQw6xrUv" }, "outputs": [], "source": [ "def random_times(p,q):\n", "# On simule selon des lois uniformes sur 1:p et 1:q\n", "# On en déduit les tirages de T_A et T_B\n", "\n", " P=np.ones(p)/p;# Loi uniforme sur 1:p\n", " Q=np.ones(q)/q;# Loi uniforme sur 1:q\n", " i_1=rand_disc(P);j_1=rand_disc(Q);\n", " i_2=rand_disc(P);j_2=rand_disc(Q);\n", "\n", " # Calcul de T_A et T_B en fonction de (i_1,j_1) (i_2,j_2)\n", " \n", " \n", " ###### A vous de jouer .....\n", " \n", " \n", " return [T_A,T_B]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "afsx0dnPxrUv", "outputId": "16118f08-3ac8-411c-a8ce-e2fcd1a9bba9" }, "outputs": [ { "data": { "text/plain": [ "[1, 1]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_times(2,3)" ] }, { "cell_type": "markdown", "metadata": { "id": "T6FZSWJMxrUw" }, "source": [ "Il ne reste plus qu'à faire suffisamment de tirages \n", "pour répondre (en partie) à la question posée." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "_ixIbTkuxrUw", "outputId": "f7d8949f-cf57-47a1-b397-cf56082101e6" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "**********************************************************************\n", "Pour p = 2, q = 3:\n", "pA = 0.277 +- 0.010, pB = 0.332 +- 0.010\n", "Il est très probable que B gagne en moyenne.\n", "**********************************************************************\n", "Pour p = 3, q = 4:\n", "pA = 0.391 +- 0.010, pB = 0.421 +- 0.010\n", "Il est très probable que B gagne en moyenne.\n", "**********************************************************************\n", "Pour p = 4, q = 5:\n", "pA = 0.444 +- 0.010, pB = 0.438 +- 0.010\n", "On ne peut pas conclure (il faut augmenter le nombre de tirages)\n", "**********************************************************************\n", "Pour p = 4, q = 4:\n", "pA = 0.366 +- 0.010, pB = 0.376 +- 0.010\n", "On ne peut pas conclure (il faut augmenter le nombre de tirages)\n" ] } ], "source": [ "def qui_gagne_MC(p,q,N):\n", " print(\"*\"*70)\n", " print(\"Pour p = {}, q = {}:\".format(p, q))\n", " statA = 0 \n", " statB = 0\n", " # Nombre de fois où chaque joueur gagne\n", " for i in range(N):\n", " [T_A,T_B] = random_times(p,q);\n", " if (T_B < T_A): # B gagne\n", " statB += 1\n", " elif (T_A < T_B): # A gagne\n", " statA += 1\n", "\n", " erreur=1/math.sqrt(N) # erreur maximum probable\n", " pA=statA/N;pB=statB/N\n", " print(\"pA = {:.3f} +- {:.3f}, pB = {:.3f} +- {:.3f}\".format(statA/N, erreur, statB/N, erreur))\n", "\n", " if (pA+erreur < pB-erreur):\n", " print(\"Il est très probable que B gagne en moyenne.\")\n", "\n", " elif (pA-erreur > pB+erreur):\n", " print(\"Il est très probable que A gagne en moyenne.\")\n", "\n", " else:\n", " print(\"On ne peut pas conclure (il faut augmenter le nombre de tirages)\")\n", "\n", "\n", "def test_1():\n", " N=10000;\n", " qui_gagne_MC(2,3,N)\n", " qui_gagne_MC(3,4,N)\n", " qui_gagne_MC(4,5,N)\n", " qui_gagne_MC(4,4,N)\n", "\n", "test_1()" ] }, { "cell_type": "markdown", "metadata": { "id": "F2QNZoixxrUw" }, "source": [ "---\n", "Exercice 4:\n", "
\n", "Noter que le théorème de la limite centrale permet (exercice!) de\n", "montrer que l'erreur \"probable maximale\" est de l'ordre de\n", "$1/\\sqrt{n}$ (C'est le même résultat qui permet d'évaluer\n", "approximativement l'erreur d'un sondage d'opinion).\n", "\n", "\n", "---\n", "\n", "Dans le cas $p=2$, $q=3$ on arrive assez facilement ($N=10000$ suffit\n", "largement) à se convaincre que $B$ gagne en moyenne. C'est plus\n", "difficile pour $(p=3,q=4)$ ($N=100000$ convient). Ça devient délicat\n", "pour $(p=4,q=5)$ (il faut prendre $N\\approx 1000000$ pour conclure que\n", "c'est $A$ qui gagne). Dans les cas où $p=q$ (où l'on peut prouver\n", "qu'il y a égalité des probabilités), une méthode de simulation ne sera\n", "__jamais__ concluante.\n", " \n", "Il nous faut une méthode exacte de calcul de ces probabilités. C'est\n", "ce que nous allons faire maintenant." ] }, { "cell_type": "markdown", "metadata": { "id": "8hFnW8eOxrUx" }, "source": [ "# 3. Un calcul exact par énumération exhaustive" ] }, { "cell_type": "markdown", "metadata": { "id": "hRxmTJ3ZxrUx" }, "source": [ "L'espace de probabilité $\\Omega$ étant fini, il suffit d'énumérer\n", "$\\Omega$ pour calculer la probabilité: on génère toutes les valeurs\n", "possibles pour les positions des oeufs $(i_1,j_1)$ et $(i_2,j_2)$\n", "(tous ces couples (de couples!) sont supposés équiprobables), on calcule $T_A$\n", "et $T_B$ et l'on fait des stats sur celui qui gagne.\n", "\n", "\n", "
\n", "On en profite pour calculer la loi du couple $(T_A,T_B)$ et pour vérifier que les\n", "lois de $T_A$ et $T_B$ sont identiques (exercice, pour une correction voir la \n", "version `scilab` du sujet).\n", "\n", "On vérifie aussi que la loi de $(T_A,T_B)$ n'est pas identique à celle de $(T_B,T_A)$ (sauf si $p=q$).\n", "On peut aussi montrer (exercice) que $T_A$ n'est jamais indépendante de $T_B$.\n", "" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "cDK7dR3hxrUx", "outputId": "81822332-8f9d-483e-f5b9-4317d10026c8" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = 40 , q = 45 : c'est A qui gagne\n", "H_AB est bien de somme 1\n", "Les lois de T_A et T_B sont bien égales.\n", "La loi du couple (T_A,T_B) n'est pas symétrique (c'est normal si p!=q) !\n", "\n" ] } ], "source": [ "def qui_gagne_elem(p,q):\n", "# On énumère toutes les positions possibles\n", "# et on en déduit lequel des joueurs gagne en moyenne\n", "\n", " Ascore=0;Bscore=0;nbre_cas_egalite=0\n", " \n", " # On génère toutes les positions pour les 2 oeufs\n", " # Attention en Python: range(1,p+1) = {1,2, ...,p}, c'est bien ce que l'on veut\n", " for i_1 in range(1,p+1) :\n", " for j_1 in range(1,q+1) :\n", " for i_2 in range(1,p+1) :\n", " for j_2 in range(1,q+1) :\n", " \n", " ###### A vous de jouer .....\n", " \n", " if T_A > T_B :\n", " Bscore=Bscore+1\n", " elif T_A < T_B:\n", " Ascore=Ascore+1\n", " else: # T_A == T_B\n", " nbre_cas_egalite=nbre_cas_egalite+1\n", "\n", " print('p = ',p,', q = ',q, ': ',end='') # end='' pour eviter le passage à la ligne\n", " if (Bscore>Ascore): \n", " print(\"c'est B qui gagne\")\n", " elif (Ascore>Bscore): \n", " print(\"c'est A qui gagne\")\n", " else: \n", " print(\"cas d'égalité\")\n", "\n", "def histo(p,q):\n", "# Calcule la loi du couple (T_A,T_B) par énumération exhaustive des cas\n", "\n", " nbre=p*q;# valeur maximale de T_A ou T_B\n", " \n", " # Les tableaux Python sont indicés à partir de 0 -> on rajoute 1\n", " H_AB=np.zeros([nbre+1,nbre+1]);\n", " \n", " # On génère toutes les positions pour les 2 oeufs\n", " for i_1 in range(1,p+1) :\n", " for j_1 in range(1,q+1) :\n", " for i_2 in range(1,p+1) :\n", " for j_2 in range(1,q+1) :\n", " \n", " \n", " ###### A vous de jouer .....\n", " \n", " \n", " # met à jour le nbre de tirages valant (k,l)\n", " H_AB[T_A,T_B] = H_AB[T_A,T_B] + 1\n", " H_AB = H_AB/(nbre*nbre) \n", " return H_AB\n", "\n", "p=40;q=45\n", "qui_gagne_elem(p,q)\n", "#samples=simul_couple(p,q)\n", "\n", "# On calcule la loi du couple (T_A,T_B)\n", "H_AB=histo(p,q)\n", "\n", "# On vérifie que H_AB est bien la loi d'un couple\n", "if np.abs(np.sum(H_AB)-1) <= 1.e-7 :\n", " print('H_AB est bien de somme 1')\n", "\n", "# Verification que les lois marginales sont identiques.\n", "###### A vous de jouer .....\n", "#H_A=...\n", "#H_B=...\n", "\n", "# H_A est forcément égal à H_B : on vérifie\n", "\n", "###### A vous de jouer .....\n", "\n", "#if ... : # H_A ?=? H_B à epsilon près ...\n", "# print(\"Warning: les lois de T_A et T_B doivent être égales.\\n\")\n", "#else:\n", "# print('Les lois de T_A et T_B sont bien égales.');\n", "\n", "\n", "# Par contre (T_A,T_B) n'a pas la meme loi que (T_B,T_A) lorsque p != q\n", "# Elles doivent l'etre!\n", "###### A vous de jouer .....\n", "#if ... : # il faut comparer la loi à sa transposée\n", " print(\"La loi du couple (T_A,T_B) n'est pas symétrique (c'est normal si p!=q) !\\n\")\n", "else:\n", " print('La loi du couple (T_A,T_B) est symétrique: p et q sont probablement égaux.');\n", "\n", "if p*q <=10:\n", " print(H_AB[1:p*q+1,1:p*q+1])" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "xh7p1YYmxrUz", "outputId": "9063b26e-0b2a-4ed4-d25f-929c48cd3d46" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = 3 , q = 4 : c'est B qui gagne\n", "p = 4 , q = 4 : cas d'égalité\n", "p = 4 , q = 5 : c'est A qui gagne\n" ] } ], "source": [ "def test_2():\n", " qui_gagne_elem(3,4);\n", " qui_gagne_elem(4,4);\n", " qui_gagne_elem(4,5);\n", " \n", " #for p in range(2,5): qui_gagne_elem(p,p+1)\n", " #for p in range(2,9): qui_gagne_elem(p,p+2)\n", " #for p in range(2,7): qui_gagne_elem(p,p+3)\n", "\n", "test_2()" ] }, { "cell_type": "markdown", "metadata": { "id": "QUy2ZA5pxrU0" }, "source": [ "On retrouve le résultat, un peu surprennant, annoncé au début." ] }, { "cell_type": "markdown", "metadata": { "id": "MtpusKb0Nsvp" }, "source": [ "# Références\n", "\n", "[Cours probabilités et statistique pour l'ingénieur - Benjamin Jourdain](http://cermics.enpc.fr/~jourdain/probastat/poly.pdf)" ] }, { "cell_type": "markdown", "metadata": { "id": "N6-F580m4DkM" }, "source": [ "## Corrigés des exercices" ] }, { "cell_type": "markdown", "metadata": { "id": "rfOrIFgS4MOk" }, "source": [ "---\n", "Exercice 1:\n", "\n", "
\n", "Lorsque la loi est uniforme sur $\\{1,\\ldots,n\\}$, on peut\n", "vérifier (exercice) que $\\E(N)=\\frac{n+1}{2}$ et $\\Var(N)=\\frac{(n+1)(n-1)}{12}$.\n", " \n", "\n", "---\n", "\n", "**Solution:**\n", "\n", "\n", "Soit $N \\sim \\mathcal{U}(\\{1, \\dots, n\\})$ \n", "\n", "On a:\n", "$$ \n", "\\begin{align}\n", " \\mathbb{E}[N] &= \\sum\\limits_{k=1}^{n} k \\underbrace{\\mathbb{P}(N = k)}_{=\\frac{1}{n}}\n", " = \\frac{1}{n} \\sum\\limits_{k=1}^{n} k \\\\\n", " &= \\frac{1}{n} \\frac{n(n+1)}{2}\n", " = \\frac{n+1}{2}\n", "\\end{align}\n", "$$\n", " \n", "$$\n", "\\begin{align}\n", " \\mathbb{E}[N^2] &= \\sum\\limits_{k=1}^{n} k^2 \\underbrace{\\mathbb{P}(N = k)}_{=\\frac{1}{n}}\n", " = \\frac{1}{n} \\sum\\limits_{k=1}^{n} k^2 \\\\\n", " &= \\frac{1}{n} \\frac{n(n+1)(2n+1)}{6}\n", " = \\frac{(n+1)(2n+1)}{6}\n", "\\end{align}\n", "$$\n", "\n", "On en déduit que:\n", "$$\n", "\\begin{align}\n", " \\mathbb{V}\\text{ar}[N] &= \\mathbb{E}[N^2] - \\mathbb{E}[N]^2 \\\\\n", " &= \\frac{(n+1)(2n+1)}{6} - \\left( \\frac{n+1}{2} \\right)^2\n", " = \\frac{(n+1)(n-1)}{12}\n", "\\end{align}\n", "$$\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "id": "1KQ9PyNZ4OQc" }, "source": [ "---\n", "Exercice 2:\n", "\n", "
\n", " Noter que l'on peut calculer la loi (commune) de $t_1^A$, $t_1^B$,\n", "$t_2^A$, $t_2^B$ (loi uniforme sur $\\{1,\\ldots,p\\times q\\}$) et\n", "montrer que $t_1^A$ s'obtient comme une permutation déterministe $\\sigma$ de\n", "$t_1^B$.\n", " \n", "\n", "---\n", "**Solution:**\n", "\n", "Les temps aléatoires $t_1^A$ et $t_1^B$ suivent tous les deux une\n", "loi uniforme sur $\\{1,\\ldots,p\\times q\\}$. \n", "\n", "En effet, si $k$ est un nombre entier compris entre $0$ et $p\\times q-1$, il s'écrit de façon unique sous la forme $k=i_1\\times p + j_1$ avec $i_1\\in\\{0,1,\\ldots,q-1\\}$ et $j_1\\in\\{0,1,\\ldots,p-1\\}$. \n", "\n", "On a donc:\n", "\n", "$$\n", "\\mathbb{P}(t_1^A=k+1) = \\mathbb{P}(V_1=i_1+1,U_1=j_1+1) = \\mathbb{P}(V_1=i_1+1)\\mathbb{P}(U_1=j_1+1) = 1/(p\\times q).\n", "$$ \n", "\n", "Ces temps ne sont pas indépendants. En fait, $t_1^B$ s'obtient par une\n", "permutation déterministe à partir de $t_1^A$: il existe une permutation\n", "$\\sigma$ de $\\{1,\\ldots,p\\;q\\}$ telle que $t_1^B=\\sigma(t_1^A).$ \n", "\n", "Il est facile de s'en convaincre, puisque à chaque case $(i,j)$\n", "correspond un temps d'atteinte différent pour chacun des joueurs:\n", "pour construite la permutation, il suffit donc de mettre en relation\n", "le temps mis par $A$ pour atteindre $(i,j)$ avec le temps mis par\n", "$B$ pour atteindre la même case. \n", "\n", "On peut aussi voir que, lorsque l'on considère le jeu avec un seul\n", "oeuf, on a toujours un problème équitable (i.e. on a $\\mathbb{P}(t_1^A < t_1^B) =\\mathbb{P}(t_1^B < t_1^A)$). \n", "\n", "Pour s'en convaincre, on écrit:\n", "\n", "$$\n", "\\mathbb{P}(t_1^A V'_1 (q-1) )\\\\\n", " &= \\mathbb{P}(t_1^B\n", "
\n", "Montrer que $T_A$ et $T_B$ ont la même loi et que si $\\sigma^2 = id$ alors les couples $(T_A, T_B)$ et $(T_b, T_A)$ ont la même loi.\n", " \n", "\n", "---\n", "**Solution:**\n", "\n", "Pour montrer que $T_A$ et $T_B$ suivent la même loi, on commence par remarquer\n", "qu'il existe une permutation $\\sigma$ de $\\{1,\\ldots,p\\times q\\}$ telle que\n", "$t^1_B=\\sigma(t^1_A)$ et $t^2_B=\\sigma(t^2_A)$ (elle est calculée\n", "plus tard, mais c'est facile de s'en convaincre). \n", "\n", "Comme $t^1_A$ et $t^2_A$ suivent des lois uniformes sur $\\{1,\\ldots,p \\times q\\}$, c'est aussi le cas de $t^1_B$ et $t^2_B$ (exercice). \n", "\n", "$t^1_B$ et $t^2_B$ sont indépendantes, puisque fonctions de variables aléatoires\n", "indépendantes. \n", "\n", "Les couples $(t^1_A,t^2_A)$ et $(t^1_B,t^2_B)$ suivent donc la même loi et l'on conclut que $T_A$ et $T_B$ ont même loi puisque:\n", "\n", "$$\n", "T_A=\\min(t^1_A,t^2_A),\\quad T_B=\\min(t^1_B,t^2_B).\n", "$$\n", "\n", "Il convient de noter que les temps aléatoires $T_A$ et $T_B$ ne sont pas indépendants. C'est d'ailleurs ce qui fait l'intérêt de\n", "la question posée (Que se passerait-il si $T_A$ et $T_B$ étaient\n", "indépendants?).\n", "\n", "\n", "On peut montrer que si $\\sigma^2=Id$, alors la loi du couple $(T_A,T_B)$ est identique à celle du couple $(T_B,T_A)$. En effet on a:\n", "\n", "$$\n", "T_A=\\min(t^1_A,t^2_A),\\quad T_B=\\min(\\sigma(t^1_A),\\sigma(t^2_A))\n", "$$\n", "\n", "Donc, en utilisant le fait que la loi de $(t^1_A,t^2_A)$ est identique à celle de $(\\sigma(t^1_A),\\sigma(t^2_A))$, on obtient:\n", "\n", "$$\n", "\\begin{align*}\n", " \\mathbb{P}\\left(T_A=k,T_B=l\\right) & = \\mathbb{P}\\left(\\min(t^1_A,t^2_A)=k,\\min(\\sigma(t^1_A),\\sigma(t^2_A))=l\\right)\\\\\n", "& = \\mathbb{P} \\left(\\min(\\sigma(t^1_A),\\sigma(t^2_A))=k, \\min(\\sigma^2(t^1_A),\\sigma^2(t^2_A))=l\\right).\n", "\\end{align*}\n", "$$\n", "\n", "Et lorsque $\\sigma^2=Id$, on en déduit $\\mathbb{P} \\left(T_A=k,T_B=l\\right) = \\mathbb{P}(T_B=k,T_A=l)$.\n", "\n", "\n", "Ceci permet d'en déduire (exercice simple mais instructif) que\n", "$$\n", "\\P(T_A